package leetcode.code0715;

public class RangeModule {

	class Node {
		private int start;
		private int end;
		private int mid;
		public Boolean trace;
		public boolean res;

		private Node left;
		private Node right;

		public Node(int start, int end) {
			this.start = start;
			this.end = end;
			this.mid = ((this.end - this.start) >> 1) + this.start;
		}

		private Node getLeft() {
			if (this.left == null) {
				this.left = new Node(this.start, this.mid);
			}
			return this.left;
		}

		private Node getRight() {
			if (this.right == null) {
				this.right = new Node(this.mid + 1, this.end);
			}
			return this.right;
		}

		public void update(int left, int right, boolean trace) {
			if (this.start == left && this.end == right) {
				this.trace = trace;
				this.res = trace;
				return;
			}
			this.pushDown();
			if (right <= mid) {
				this.getLeft().update(left, right, trace);
			} else if (left >= this.mid + 1) {
				this.getRight().update(left, right, trace);
			} else {
				this.getLeft().update(left, this.mid, trace);
				this.getRight().update(this.mid + 1, right, trace);
			}
			this.res = this.getLeft().res && this.getRight().res;
		}

		private void pushDown() {
			if (this.trace != null) {
				this.getLeft().trace = this.trace;
				this.getLeft().res = this.trace;
				this.getRight().trace = this.trace;
				this.getRight().res = this.trace;
				this.trace = null;
			}
		}

		public boolean query(int left, int right) {
			if (this.start == left && this.end == right) {
				return this.res;
			}
			this.pushDown();
			if (right <= mid) {
				return this.getLeft().query(left, right);
			} else if (left >= this.mid + 1) {
				return this.getRight().query(left, right);
			} else {
				return this.getLeft().query(left, this.mid) && this.getRight().query(this.mid + 1, right);
			}
		}

	}

	Node root;

	public RangeModule() {
		root = new Node(1, (int) 1e9 - 1);//
	}

	public void addRange(int left, int right) {
		root.update(left, right - 1, true);
	}

	public boolean queryRange(int left, int right) {
		return root.query(left, right - 1);
	}

	public void removeRange(int left, int right) {
		root.update(left, right - 1, false);
	}

	public static void main(String[] args) {
		RangeModule rm = new RangeModule();
//		rm.addRange(10, 20);// null
//		rm.removeRange(14, 16);// null
//		boolean b = false;
//		b = rm.queryRange(10, 14);// true （区间 [10, 14) 中的每个数都正在被跟踪）
//		System.out.println(b);
//		b = rm.queryRange(13, 15);// false （未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
//		System.out.println(b);
//		b = rm.queryRange(16, 17);// true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
//		System.out.println(b);
		boolean b = false;
		rm.addRange(10, 180);
		rm.addRange(150, 200);
		rm.addRange(250, 500);
		b = rm.queryRange(50, 100);
		System.out.println(b);
		b = rm.queryRange(180, 300);
		System.out.println(b);
		b = rm.queryRange(600, 1000);
		System.out.println(b);
		rm.removeRange(50, 150);
		b = rm.queryRange(50, 100);
		System.out.println(b);
//		["RangeModule","addRange","addRange","addRange","queryRange","queryRange","queryRange","removeRange","queryRange"]
//		[[],[10,180],[150,200],[250,500],[50,100],[180,300],[600,1000],[50,150],[50,100]]
		// [null,null,null,null,true,true,false,null,false]
//		[null,null,null,null,true,false,false,null,false]

	}

}
